//输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 
//
// 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 
//
// 
//
// 示例 1： 
//
// 输入：target = 9
//输出：[[2,3,4],[4,5]]
// 
//
// 示例 2： 
//
// 输入：target = 15
//输出：[[1,2,3,4,5],[4,5,6],[7,8]]
// 
//
// 
//
// 限制： 
//
// 
// 1 <= target <= 10^5 
// 
//
// 
//
// Related Topics 数学 双指针 枚举 👍 537 👎 0


package leetcode.editor.cn;

// [剑指 Offer 57 - II]和为s的连续正数序列

import java.util.ArrayList;
import java.util.Arrays;

public class HeWeiSdeLianXuZhengShuXuLieLcof_JianZhiOffer57II {
    public static void main(String[] args) {
        Solution solution = new HeWeiSdeLianXuZhengShuXuLieLcof_JianZhiOffer57II().new Solution();
        int[][] ans = solution.findContinuousSequence(98160);
        for (int i = 0; i < ans.length; i++) {
            System.out.println(Arrays.toString(ans[i]));
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] findContinuousSequence(int target) {
            ArrayList<int[]> ans = new ArrayList<>();
            int i = 1, j = 2;
            while (j <= (target >> 1) + 1) {
                int num = (i + j) * (j - i + 1);
                if (num > 2 * target) {
                    i++;
                } else if (num < 2 * target) {
                    j++;
                } else {
                    int[] ints = new int[(int) j - (int) i + 1];
                    for (int k = 0; k <= j - i; k++) {
                        ints[k] = k + i;
                    }
                    ans.add(ints);
                    i++;
                }
            }
            return ans.toArray(new int[ans.size()][]);
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    class Solution1 {
        public int[][] findContinuousSequence(int target) {
            ArrayList<int[]> ans = new ArrayList<>();
            for (long a = 1; a <= (target >> 1); a++) {
                double b = (-1 + Math.sqrt(1 - 4 * (a - (a * a) - 2 * target))) / 2;
                if (b == (int) b) {
                    int[] ints = new int[(int) b - (int) a + 1];
                    for (int i = 0; i <= b - a; i++) {
                        ints[i] = i + (int) a;
                    }
                    ans.add(ints);
                }
            }
            return ans.toArray(new int[ans.size()][]);
        }
    }
}